package com.jiangwz.avl;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author jiangwz
 * @create 2019/10/8.
 */
public class AVLTreeDemo {

    public static void main(String[] args) {
//        int[] arr = {4, 3, 6, 5, 7, 8};
        int[] arr = { 10, 11, 7, 6, 8, 9 }; // 运行原来的代码可以看到，并没有转成 AVL树.
//        int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树
        AVLTree tree = new AVLTree();
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }

//        tree.inOrder();
        tree.levelOrder();
        System.out.println(tree.getRoot().height());
        System.out.println(tree.getRoot().leftHeight());
        System.out.println(tree.getRoot().rightHeight());

    }


}

class AVLTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    public void add(Node node) {
        if (node == null) return;
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void inOrder() {
        root.inOrder();
    }

    /**
     * 层序遍历
     */
    public void levelOrder() {
        root.levelOrder();
    }
}

class Node {
    private int val;
    private Node left;
    private Node right;

    public Node(int val) {
        this.val = val;
    }


    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    public void add(Node node) {
        if (this.val > node.val) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }

        if (rightHeight() - leftHeight() > 1) {
            // 左旋转
            if (right != null && right.leftHeight() > right.rightHeight()) {
                right.rotateRight();
            }
            rotateLeft();
            return;
        }
        if (leftHeight() - rightHeight() > 1) {
            //右旋转
            if (left != null && left.rightHeight() >left.leftHeight()) {
                left.rotateLeft();
            }
            rotateRight();
            return;
        }



    }

    private void rotateLeft() {
        Node newNode = new Node(this.val);
        newNode.left = this.left;
        newNode.right = this.right.left;
        this.val = this.right.val;
        this.right = this.right.right;
        this.left = newNode;
    }

    private void rotateRight(){
        Node newNode = new Node(this.val);
        newNode.right = this.right;
        newNode.left = this.left.right;
        this.val = this.left.val;
        this.left = this.left.left;
        this.right = newNode;
    }

    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    public void inOrder() {
        if (this.left != null) {
            this.left.inOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.inOrder();
        }
    }

    public int leftHeight() {
        if (this.left == null) {
            return 0;
        }
        return this.left.height();
    }

    public void levelOrder(){
        Queue<Node> q = new LinkedList<>();
        q.add(this);
        while (!q.isEmpty()) {
            Node poll = q.poll();
            System.out.println(poll);
            if (poll.left != null) q.add(poll.left);
            if (poll.right!= null) q.add(poll.right);
        }
    }

    public int rightHeight(){
        if (this.right == null) {
            return 0;
        }
        return this.right.height();
    }
}

